package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.ArrayList;

/**
 * @author lixiaowen
 * @create 2019-12-16
 */
public class SecondMinimumNodeInaBinaryTree671 {

    public int findSecondMinimumValue(TreeNode root) {
        int MIN = root.val;
        int secondMinVal = findSecondMinimumValue(root, MIN);
        return secondMinVal != MIN ? secondMinVal : -1;
    }

    /**
     * 1.若子树中大于全局MIN, 返回大于MIN的最小值
     * 2. 若子树中全为MIN，返回MIN
     *
     * @param node
     * @param MIN
     * @return
     */
    private int findSecondMinimumValue(TreeNode node,final int MIN){
        if (node == null) return MIN;
        //因为根的结点是子树的最小值，若当前子树的根比最小值还小，那么子树根节点的值可以返回【减枝】
        if(node.val > MIN ||  node.left == null || node.right == null ) return node.val;
        int left = findSecondMinimumValue(node.left,MIN);
        int right = findSecondMinimumValue(node.right,MIN);
        //此时 node.val == min，求倒数第二小的数据，注意left和right是否有min
        int smaller = Math.min(left, right);
        return smaller == MIN ? Math.max(left, right) : smaller;
    }
}
